模拟赛题解/2025.10.16 模拟赛

T1-签到题（easy）

题面

给定长度为 $n$ 的数组 $a$ 和长度为 $m$ 的数组 $b$，构建大小为 $n \times m$ 的网格，其中单元格 $(x, y)$ 中的值为 $C_{x,y} = a_x + b_y$。

从 (1, 1) 开始，每一步都要选择一个位于右下方的网格单元格进行移动，直到到达 $(n, m)$，目标是最大化路径上相邻单元格之间的绝对差值之和。

从形式上看，您的目标是找到满足以下条件的序列 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$：

• $(x_1, y_1) = (1, 1)$
• $(x_k, y_k) = (n, m)$
• $x_i \leq x_{i+1}, \, y_i \leq y_{i+1}, \, (x_i, y_i) \neq (x_{i+1}, y_{i+1}) \, \forall i \in [1, k)$

同时使 $\sum_{i=1}^{k-1} |C_{x_i, y_i} - C_{x_{i+1}, y_{i+1}}|$ 最大化。

$1\leq n,m,a_i,b_i\leq 10^5$。

题解

相邻两个不同的限制是无所谓的，因为对答案没有影响。又因为根据绝对值的性质，有 $|A - B| \leq |A - C| + |C - B|$，所以可以发现每次往右或往下走一步是最优的。

而由于权值 $C_{x,y} = a_x + b_y$，所以 $|C_{x',y'} - C_{x,y}|$ 实际等于 $|a_{x+1} - a_x|$ 或 $|b_{y+1} - b_y|$，并且无论路径如何，答案都等于 $\sum_{i=1}^{n-1} |a_{i+1} - a_i| + \sum_{i=1}^{m-1} |b_{i+1} - b_i|$，故直接输出即可。

时间复杂度 $O(n + m)$。

T2-简单题（simple）

题面

给定一棵 $n$ 个点的树，问有多少个非空路径集合，使得集合内的路径的点集的交非空，答案对 $998244353$ 取模。

在本题中，我们认为路径的两个端点不能相同，且我们不区分端点的顺序，即路径 $(1,2)$ 和路径 $(2,1)$ 我们认为是一样的。

$1\leq n\leq 10^6$。

题解

考虑到路径的交一定是一条路径，于是想到点减边容斥，于是只需要单独考虑所有点和边，计算被所有 路径覆盖的方案即可。

时间复杂度 $O(n\log n)$。

T3-入门题（basic）

题面

定义一个序列 $a_1, a_2, \ldots, a_m$ 是好的当且仅当满足以下条件：

• $a_i > 0$
• $\forall 1 \leq i \leq m - 1, |a_i - a_{i+1}| = 1$
• $\sum_{i=1}^m a_i = n$

对于一个序列 $a_1, a_2, \ldots, a_m$，定义

$f(a) = \sum_{i=1}^{m-1} [a_i > a_{i+1}]$

求所有好的序列的 $c^{f(a)}$ 之和，对 $998244353$ 取模。

在本题中，我们认为 $0^0 = 1$。

$1\leq n\leq3\times10^5,0\leq c<998244353$。

题解

Sub 2

记 $f_{i,j,k}$ 表示当前序列长度为 $i$ 和为 $j$，最后一个数为 $k$ 的权值之和。

复杂度 $O(n^3)$。

Sub 3

记 $f_{i,j}$ 表示当前序列和为 $i$，最后一个数为 $j$ 的权值和。

复杂度 $O(n^2)$。

Sub 4

注意到，序列长度和值域不能同时太大，于是考虑按 $a_1$ 的大小分类。

记 $S$ 表示最小的使得 $\frac{S \times (S+1)}{2} > n$ 的数。

若 $a_1 < S$ 直接跑 $Sub3$ 的 $DP$，复杂度 $O(n^{1.5})$。

若 $a_1 \geq S$ 则不用考虑 $a_i > 0$ 的限制，约定 $a_1 = 0$，枚举长度后直接跑 $Sub2$ 的 $DP$。

总复杂度 $O(n^{\frac{8}{5}})$。

Sub 5

考虑优化 $a_1 \geq S$ 部分的 $DP$，为了第二部分可以不计最后一个数是多少，于是考虑倒着加数，由于我们确定了 $a_1 = 0$，于是往前加一个数的贡献就是整体上移或下移，于是可以优化到 $O(n^{1.5})$。

T4-送分题(freebie)

题面

小 A 和小 B 将玩一个游戏。

初始时，有一个可重集，每轮开始时，双方各选择一个元素，但是双方都不知道对方的选择。

若双方的选择相同（注意，并不是指值相同。如 $\{1, 1\}$，我们认为选择第一个 1 和选择第二个 1 是不同的选择），则将这个元素删除。此时，若可重集内没有元素，则游戏结束，否则，继续下一轮。

若选择不同，则小 A 得到这个元素的值的分数，并结束游戏。

小 A 想让自己的得分最大化，小 B 想让小 A 的得分最小化，若双方都足够聪明，求最终小 A 得分的期望。

相对或绝对误差小于 $10^{-6}$ 则视为正确。

$1\leq n\leq22$，可重集内元素 $\in[1,10^9]$。

题解

首先，小B的策略一定是基于概率的，即对于一个局面，小B会对于每个物品都有一个概率表示当前局面下选这个物品的概率，然后按概率随机选择一个。

考虑状压 DP，令 $f_S$ 表示还剩 $S$ 以内的题没被选中时你的期望得分的最大值，不妨令 $b_i$ 表示除去 $i$ 题后期望得分的最大值，即 $f_{S|i}$，$p_i$ 表示小B选中第 $i$ 题的概率，那么有转移：

$f_S = \min_{p_1 + \cdots + p_{|S|}=1} \max_i (p_i b_i + (1 - p_i) a_i)$

不妨将 $a_i$ 从大到小排序，其一定满足 $\forall i \leq j, b_i \leq b_j$，先让所有 $p_i \leftarrow 0$，令 $c_i$ 表示当前的 $p_i b_i + (1 - p_i) a_i$，那么初始有 $c_i = a_i$，接下来一步步调整 $p_i$，看 $\max c_i$ 能取到的最小值，如果某个时刻 $\sum p_i > 1$，那么撤回这一步骤作，将 $1 - \sum p_i$ 平均分配到前面这些 $c_i$ 中。如果有 $a_i \leq b_i$，那么 $\max c_i$ 的最小值只能是 $a_i$。

直接模拟上面的过程即可，时间复杂度 $O(n2^n)$。